Neural Information Processing Systems http://nips.cc/

We consider the Threshold Bandit setting, a variant of the classical multi-armed bandit problem in which the reward on each round depends on a piece of side information known as a threshold value .

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. Summary: ******* The paper considers the following general sequential learning problem: a set of actions \cal{A} and a parametric set F of bounded functions mapping actions to the reals are given. At each time step, a subset \cal{A}_t \subset \cal{A} is provided, one has to choose one action A_t in \cal{A}_t, and then gets a reward R_t. The reward is assumed to come from a sub-Gaussian distribution with mean f_\theta(A_t), where f_\theta \in F is a fixed, unknown, function. The authors then introduce in Section 4 the notion of eluder-dimension that is designed to capture how difficult it is to infer the value of one action from previously observed ones.